package com.origin.niuke.linkedlist;

import general_class.ListNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/27 12:14
 * 删除链表的倒数第n个节点
 * 算法：链表 + 快慢指针
 * 给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
 * 快指针走 n 步，然后再慢指针走
 */
public class NC53 {

    public ListNode removeNthFromEnd (ListNode head, int n) {
        ListNode dummy = new ListNode(-1), slow = head, fast = head;
        dummy.next = head;
        while (fast != null && n-- >= 0) fast = fast.next;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        if (slow != null) slow.next = slow.next.next;
        return dummy.next;
    }

}
